/*==============
 * 边界标识法
 *
 * 包含算法: 8.1
 ===============*/

#ifndef BOUNDARYTAGMETHOD_H
#define BOUNDARYTAGMETHOD_H

#include <stdio.h>
#include <stdlib.h>
#include "Status.h"     //**▲01 绪论**//

/* 宏定义 */
#define e 5                        // 分配空间时用到的容差
#define FootLoc(p) p+(p->size)-1   // 将p指针定位到p所指内存块的底部


/*
 * 内存"字"的类型定义
 *
 * 所谓"字"是指空间分配的最小单位，它不是字节。
 * 一个"字"有多大，取决于对"字"结构是如何定义的。
 */
typedef struct WORD {
    
    /*
     * 注：
     * 教材中将llink和uplink封装在了一个联合体中，个人感觉这个封装有些鸡肋。
     * 一方面，head和foot的公共部分其实只有tag，如果真想用联合体，那么应当把size和rlink也封装起来。
     * 另一方面，这个封装节省的空间很有限，而且直接影响了代码的可读性。
     * 这里只是教学代码，而不是真实的系统代码，所以空间考虑在其次，原理展示为首要任务。
     * 此外，教材中的伪码中也并没有考虑这个联合体，而是直接进行操作的。
     * 综上所述，这里去除了教材中的联合体结构。
     * 如想观察带有联合体的写法，可以参考CFree分支的代码。
     */

    int tag;             // 块标志，0空闲，1占用，头部和尾部均有
    
    struct WORD* llink;  // 头部域，指向前驱结点
    struct WORD* rlink;  // 头部域，指向后继结点
    int size;            // 头部域，块大小
    
    struct WORD* uplink; // 底部域，指向本结点头部
} WORD;

typedef WORD* Space;     // Space：指向可利用空间的指针类型


/*
 * 初始化一块大小为n个字的内存，并返回指向该内存的起点的指针
 * 注：返回的初始内存已经包含了head和foot。
 */
Space InitSpace(int n);

/*
 * ████████ 算法8.1 ████████
 *
 * 边界标识法的内存分配算法
 *
 * 从空间pav中申请一块大小至少为n的空间，并返回指向申请到的空间的指针。如果分配失败，则返回NULL。
 * 为了使分配后的剩余块尽量均匀分布，每次分配完之后都要把空间指针pav向前移动，具体描述参见教材。
 *
 * 注：
 * 1.这里采用首次拟合法，即一遇到满足条件的内存块就进行分配操作。
 * 2.为了避免空间碎片化过快，这里增加了一个容差e，具体含义参考教材描述。
 * 3.这里申请分配n个字的空间，指的是已经完成换算的空间。
 *   比如用户想要容量为10个字的空间，但每个空间又包含head和foot这两个字存储空间使用信息，
 *   因此实际上分配的空间大小应为12个字，这个"12"就是n的含义。
 *   教材中提到"head和foot在分配时忽略不计"，这样是为了伪码书写的方便。实际写代码时，这两个空间是不能忽略的。
 *   但是如果按照上面的描述，把n解释为已经换算后空间，而不是用户原始申请的空间，
 *   那么既满足了没有忽略空间，又满足了在书面效果上，跟教材伪码统一，可谓两全其美。
 */
Space AllocBoundTag(Space* pav, int n);

/*
 * 边界标识法的内存回收算法
 *
 * 对指针p处的内存进行释放
 */
void FreeBoundTag(Space* pav, Space p);

/*
 * 打印内存布局，查看当前内存的使用情况
 * 注：仅限内部测试使用
 */
void PrintMemoryLayout();

/*
 * 计算可用的空闲空间容量
 *
 * 注：仅限内部使用，用在日志打印中
 */
static int AvailableSpace(Space pav);

#endif
